Modern microprocessors often use a cache hierarchy. In a hierarchy of caches, inner caches, those more closely connected to a processor, may give rapid access to instructions and data but may have limited storage capacity. Outer caches, those more closely connected to system memory, may have much larger storage capacity but much larger latency for requests from the processor. No matter whether they are inner caches or outer caches, caches generally face the problem of the replacement of cache lines that are no longer needed with new cache lines representing newer memory requests from the processor. When there are cache lines in an invalid state, these may be replaced with new cache lines without much system performance impact. But when no cache lines are in an invalid state, the cache control logic must pick a cache line in a valid state, called a victim cache line, and overwrite it with the new cache line. This presents a system performance issue in that a cache line discarded as a victim may soon be requested again by the processor, and may need to be fetched once again.
There are several existing methods of selecting a victim cache line when needed. One commonly used one is the least-recently-used (LRU) method, where the cache line selected as the victim cache line is the one which has been unused for the longest time. However, when used in an outer cache, the LRU method may give poor results because what may be important is which cache lines have been unused by the inner caches, and the outer caches may not have access to this information. Similarly, random victim selection and first-in-first-out (FIFO) victim selection methods may have drawbacks.
One approach to dealing with poorly-chosen victim cache lines utilizes a small buffer called a victim cache, connected between its related cache and the refill path. The victim cache may contain the victim cache lines that were recently overwritten in the related cache. The victim cache may be checked on a cache line miss, and if found in the victim cache the requested cache line may be swapped with another cache line in the related cache. This may reduce the latency of fetching the requested cache line from more outer caches or system memory, but at the cost of the complexity of the victim cache and its associated logic. As the victim cache may need to ensure cache coherency, this cost may be relatively high.